#pragma once

#include "iostream"
#include "vector"
#include "algorithm"
#include "TypeDefin.h"
#include "queue"
using namespace std;
/*HJJ QQ479287006
 *给你一棵 完美 二叉树的根节点 root ，请你反转这棵树中每个 奇数 层的节点值。

例如，假设第 3 层的节点值是 [2,1,3,4,7,11,29,18] ，那么反转后它应该变成 [18,29,11,7,4,3,1,2] 。
反转后，返回树的根节点。

完美 二叉树需满足：二叉树的所有父节点都有两个子节点，且所有叶子节点都在同一层。

节点的 层数 等于该节点到根节点之间的边数。
输入：root = [2,3,5,8,13,21,34]
输出：[2,5,3,8,13,21,34]
解释：
这棵树只有一个奇数层。
在第 1 层的节点分别是 3、5 ，反转后为 5、3 。

 * */

void reverseOddLevels_ru(TreeNode* &root,int h) {
    if (root==nullptr)
        return ;

    //如果是基数节点交换 初始为0
     if(h%2==0&&root->right&&root->left){
         int temp=root->right->val;
         root->right->val=root->left->val;
         root->left->val=temp;
     }

    reverseOddLevels_ru(root->left,h+1);
    reverseOddLevels_ru(root->right,h+1);

}


//层次遍历然后求个高度 如果下一层就交互
TreeNode* reverseOddLevels(TreeNode* root) {
    queue<TreeNode*> que;
    if (root != NULL) que.push(root);
    vector<vector<TreeNode*>> result;
    while (!que.empty()) {
        int size = que.size();
        vector<TreeNode*> vec;
// 这⾥⼀定要使⽤固定⼤⼩size，不要使⽤que.size()，因为que.size是不断变化的
        for (int i = 0; i < size; i++) {
            TreeNode* node = que.front();
            que.pop();
            vec.push_back(node);
            if (node->left) que.push(node->left);
            if (node->right) que.push(node->right);
        }
        result.push_back(vec);
    }


    for (int i = 0; i <result.size() ; ++i) {
        if (i%2!=0)
        {
            int low=0;
            int high=result[i].size()-1;
            while (low<=high)
            {
                int temp=result[i][high]->val;
                result[i][high]->val=result[i][low]->val;
                result[i][low]->val=temp;
                high--;
                low++;
            }


        }

    }


    return root;

}

//[0,2,1,0,0,0,0,2,2,2,2,1,1,1,1]